#pragma once

#include "typedefs.h"
#include "poly_bezier_builder_base.h"
#include <boost/shared_ptr.hpp>

namespace outline {

struct length_record {
	uint min_start;
	uint max_start;
	bool can_be_closed;	//can this part be closed by addition of single Bezier polynomial
	uint scount() const
		{ return max_start - min_start + 1; }
};

/// length table describes last part of open spline for each acceptable length of that part
class length_table 
{
public:
	length_table(uint s = 0, uint m = 0) : size(s), max_estimated_length(m)
		{ }
	void reset(uint s, uint m) 
		{ size = s; max_estimated_length = m; }
	length_record operator [] (uint l) const;
	uint min_length() const
		{ return 4; }
	uint max_length() const
		{ return size - 2; }
public:
	uint size;
	uint max_estimated_length;
};

struct junction_record {
	uint min_len; //of open spline
	uint max_len;
	bool can_be_closed;	//can spline with given number of junctions be closed by addition of single Bezier polynomial
	uint lcount() const
		{ return max_len - min_len + 1; }
};

/// junction table describes open spline for each acceptable number of junctions
class junction_table  
{
public:
	junction_table(uint size = 0, uint max_estimated_length = 0)
		{ reset(size, max_estimated_length); }
	void reset(uint size, uint max_estimated_length);
	junction_record const & operator [] (uint j) const
		{ return vec_[j]; }
	uint size() const
		{ return vec_.size(); }
	uint min_jcount() const
		{ return min_jcount_; }
private:
	uint min_jcount_;
	std::vector<junction_record> vec_;
};

template <typename R>
struct grand_params : poly_bezier_builder_params<R> 
{
	unsigned min_junctions;
	unsigned max_junctions;
	R penalty_for_each_junction;
	void put_within_the_limits();
};

template <typename T, typename R = typename type_traits<T>::real_type>
class grand_poly_bezier_builder2 : public poly_bezier_builder_base<T, R>
{
public:
	void reset(nodes_type const & polyline);
	void reset_estimations(); ///< forgets results of all estimations and their consequences (assembling)
	void reset_assemblings(); ///< forgets assemblings of spline from several Bezier pieces only
	void set_params(grand_params<R> params); ///< may ivalidate estimations or assemblings

	///inspects all Bezier pieces of one more length
	void estimate_more();
	uint max_estimated_length() const
		{ return max_estimated_length_; }
	uint max_piece_length() const
		{ return size_ + 1; }
	bool all_lengths_estimated() const
		{ return max_estimated_length_ >= size_ + 1; }

	void estimate_one();
	uint max_estimated_start() const
		{ return max_estimated_start_; }
	uint max_start() const
		{ return size_; }
	bool all_starts_estimated() const
		{ return max_estimated_start_ >= size_; }

	///analyzes routes with one more junction
	void assemble_more();
	uint max_assembled_junctions() const //in closed spline
		{ return jvec_.size() + 1; }
	uint max_allowed_junctions() const
		{ return std::max(junction_table_.min_jcount() + 2, std::min(junction_table_.size() + 1, params_.max_junctions)); }
	bool all_junctions_assembled() const
		{ return max_estimated_length_ == 3 || max_assembled_junctions() >= max_allowed_junctions(); }

	bool estimated_and_assembled() const
		{ return all_lengths_estimated() && all_junctions_assembled(); }

	std::vector<uint> const & candidates() const
		{ return candidate_; }

public:
	virtual R select_best(index_vector_type & ivec);
	virtual grand_params<R> const & get_params() const
		{ return params_; }
	estimation_type const & inline_get_estimation(uint begin, uint len) const;
	virtual estimation_type const & get_estimation(uint begin, uint len, uint) const;
	virtual void get_junction_types(index_vector_type const & ivec, std::vector<junc_type> & junc) const;

private:
	/// for each junction count, start node and length of open spline this information is stored
	struct route {
		R d; ///< total discrepancy of the route, including penalties
		uint second; ///< second node on the route
	};
	/// a vector containg routes with equal lengths, but distinct beginnings
	typedef std::vector<route> unilength_routes;
	/// a matrix containg routes with equal junctions count, but distinct lengths and beginnings
	typedef std::vector<unilength_routes> unijunction_routes;
	typedef boost::shared_ptr<unijunction_routes> unijunction_routes_sptr;

private:
	void init_jvec();
	unijunction_routes & append_jvec();
	route & get_jvec_at(uint j, uint l, uint b);

private:
	struct step {
		R d;
		uint next; ///index of the following step or ~0
		step() { }
		step(R dd, uint nn) : d(dd), next(nn) { }
	};
	typedef std::vector<step> partition; ///< first step contains discrepancy of entire partition
	/// computes partition of the polyline starting from node 'begin' on the pieces of sizes from 4 to 6 
	void closed_partition(uint begin, uint min_len, partition & p);

private:
	grand_params<R> params_;
	uint max_estimated_length_;
	uint max_estimated_start_;
	/// size_ * (length_-3) elements
	/// estimations_[b][l].d says that
	/// piece of nodes starting from node b and ending (including) at node b+l+5 may
	/// be approximated with that discrepancy;
	/// very probably that satisfied estimations_[b][0].d = 0 (len=4) for all b's
	estimation_matrix_type estimations_; 

	/// initializes in estimate_more(...)
	length_table length_table_;
	junction_table junction_table_;

	std::vector<unijunction_routes_sptr> jvec_;

	std::vector<uint> candidate_; ///< list of nodes, that are candidates for a junction
};

//inlines

template <typename T, typename R>
inline typename grand_poly_bezier_builder2<T,R>::estimation_type const & 
grand_poly_bezier_builder2<T,R>::inline_get_estimation(uint begin, uint len) const
{
	assert(begin < size_);
	assert(len >= 4 && len <= max_estimated_length_);
	return estimations_[begin][len-4];
}

template <typename T, typename R>
inline typename grand_poly_bezier_builder2<T,R>::route & 
grand_poly_bezier_builder2<T,R>::get_jvec_at(uint j, uint l, uint b)
{
	assert (j < jvec_.size());
	assert (l >= junction_table_[j].min_len && l <= junction_table_[j].max_len);
	assert (b >= length_table_[l].min_start && b <= length_table_[l].max_start);
	return (*jvec_[j])[l - junction_table_[j].min_len][b - length_table_[l].min_start];
}

} //namespace outline
